//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：digits = "23"
//输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 
//
// 示例 2： 
//
// 
//输入：digits = ""
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：digits = "2"
//输出：["a","b","c"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= digits.length <= 4 
// digits[i] 是范围 ['2', '9'] 的一个数字。 
// 
//
// Related Topics 哈希表 字符串 回溯 👍 2594 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-08-26 02:23:13
 * @description 17.电话号码的字母组合
 */
public class LetterCombinationsOfAPhoneNumber{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new LetterCombinationsOfAPhoneNumber().new Solution();
		 System.out.println(solution.letterCombinationsP2("23").toString());
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	List<String> res = new ArrayList<>();
	public List<String> letterCombinations(String digits) {
		int n = digits.length();
		if (n == 0) return res;
		Map<Character, char[]> map = new HashMap<>();
		map.put('2', new char[]{'a', 'b', 'c'});
		map.put('3', new char[]{'d', 'e', 'f'});
		map.put('4', new char[]{'g', 'h', 'i'});
		map.put('5', new char[]{'j', 'k', 'l'});
		map.put('6', new char[]{'m', 'n', 'o'});
		map.put('7', new char[]{'p', 'q', 'r', 's'});
		map.put('8', new char[]{'t', 'u', 'v'});
		map.put('9', new char[]{'w', 'x', 'y', 'z'});
		backtrack(digits, new StringBuilder(), map, 0, n);
		return res;
	}

	private void backtrack(String digit,StringBuilder path,Map<Character,char[]>map,int dep,int n){
		//如果放置完了就返回
		if(dep==n){
			res.add(new String(path));
			return;
		}
		//取出当前数字的字母
		char c = digit.charAt(dep);
		char[] chars = map.get(c);
		//依次赋值
		for (int i = 0; i < chars.length; i++) {
			path.append(chars[i]);
			//放置下一个位置
			backtrack(digit,path,map,dep+1,n);
			//恢复现场
			path.deleteCharAt(dep);
		}
	}

	/*队列实现*/

	public  List<String> letterCombinations1(String digits) {
		List<String> queue = new LinkedList<String>();
		List<String> phone=new ArrayList<>();
		if(digits.length()==0)
		{
			return queue;
		}
		phone.add("abc");
		phone.add("def");
		phone.add("ghi");
		phone.add("jkl");
		phone.add("mno");
		phone.add("pqrs");
		phone.add("tuv");
		phone.add("wxyz");
		//第一个数字的位置
		int index0=digits.charAt(0)-'0';
		//第一个数字代表的字符串
		String abc0=phone.get(index0-2);
		for(int k=0;k<abc0.length();k++)
		{
			//加入队列
			String ll=abc0.substring(k,k+1);
			queue.add(ll);
		}

		for(int i=1;i<digits.length();i++)
		{
			//从第二个位置开始放置
			int index=digits.charAt(i)-'0';
			//获取第下一个位置的字母数组
			String abc=phone.get(index-2);
			int current=queue.size();
			//前一个字母的种类就是队列的size
			//当前放置的字母的可能性就是abc.length
			for(int l=0;l<current;l++)
			{
				for(int k=0;k<abc.length();k++)
				{
					//拼接后加入新的组合
					String ll=queue.get(0)+abc.substring(k,k+1);
					queue.add(ll);
				}
				//然后把这个之前那个去掉
				queue=queue.subList(1,queue.size());
			}

		}
		//循环完正好所有位置都放完了
		return queue;
	}

	/**
	 * 回溯
	 * */
	public List<String> letterCombinationsP1(String digits){
		List<String> res=new ArrayList<>();
		if(digits.length()==0)return res;
		Map<Character,char[]> dict=Map.of(
			'2', new char[]{'a', 'b', 'c'},
		'3', new char[]{'d', 'e', 'f'},
		'4', new char[]{'g', 'h', 'i'},
		'5', new char[]{'j', 'k', 'l'},
		'6', new char[]{'m', 'n', 'o'},
		'7', new char[]{'p', 'q', 'r', 's'},
		'8', new char[]{'t', 'u', 'v'},
		'9', new char[]{'w', 'x', 'y', 'z'});
		backtrack(digits,new StringBuilder(),res,dict);
		return res;
	}
	public void backtrack(String digits,StringBuilder path,List<String> res,Map<Character,char[]> dict){
		if(path.length()==digits.length()){
			res.add(new String(path));
			return;
		}
		char[] chars = dict.get(digits.charAt(path.length()));
		for (int i1 = 0; i1 < chars.length; i1++) {
			path.append((chars[i1]));
			backtrack(digits,path,res,dict);
			path.deleteCharAt(path.length()-1);
		}
	}

	public List<String> letterCombinationsP2(String digits){
		List<String> res=new LinkedList<>();
		List<String> phone=new ArrayList<>();
		if(digits.length()==0)return res;
		phone.add("abc");
		phone.add("def");
		phone.add("ghi");
		phone.add("jkl");
		phone.add("mno");
		phone.add("pqrs");
		phone.add("tuv");
		phone.add("wxyz");
		String s = phone.get(digits.charAt(0) - '2');
		for (int i = 0; i < s.length(); i++) {
			res.add(s.substring(i,i+1));
		}
		for (int i = 1; i < digits.length(); i++) {
			String s1 = phone.get(digits.charAt(i) - '2');
			int size= res.size();
			for (int i1 = 0; i1 < size; i1++) {
				for (int i2 = 0; i2 < s1.length(); i2++) {
					res.add(res.get(0)+s1.charAt(i2));
				}
				res.remove(0);
			}
		}
		return res;
	}
	 }
//leetcode submit region end(Prohibit modification and deletion)

}
